#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_set>
using namespace std;


struct TreeNode{
    int val;
    TreeNode* left;
    TreeNode* right;
    TreeNode(int x):val(x), left(nullptr), right(nullptr){}
};

class Solution{
    private:
    unordered_map<int, int> index;

    public:
    
    TreeNode* ans1(vector<int>& preorder, vector<int>& inorder){
        int len = preorder.size();
        for(int i = 0; i != len; i++){
            index[inorder[i]] = i;
        }
        return build(preorder, inorder, 0, len-1, 0, len-1);
    }

    TreeNode* build(vector<int>& preorder, vector<int>& inorder, int pre_left, int pre_right, int in_left, int in_right){
        if(pre_left > pre_right){
            return nullptr;
        }
        int pre_root = pre_left;
        int in_root = index[preorder[pre_root]];

        TreeNode* root = new TreeNode(preorder[pre_root]);
        int left_size = in_root - in_left;
        root->left = build(preorder, inorder, pre_left+1, pre_left+left_size, in_left, in_root-1);
        root->right = build(preorder, inorder, pre_left+left_size+1, pre_right, in_root+1, in_right);

        return root;
    }

    void frontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            return;
        }
        val.push_back(root->val);
        frontTraverse(root->left, val);
        frontTraverse(root->right, val);
    }

    void myfrontTraverse(TreeNode* root, vector<int>& val){
        if(root == nullptr){
            val.push_back('#');
            return;
        }
        val.push_back(root->val);
        myfrontTraverse(root->left, val);
        myfrontTraverse(root->right, val);
    }

    void show(vector<int>& val){
        int len = val.size();
        for(int i = 0; i != len-1; i++){
            cout << val[i] << " " << ends;
        }
        cout << val[len-1] << endl;
        val.clear();
    }

};

void test1(){
    Solution s;

    vector<int> preorder = {3,9,20,15,7};
    vector<int> inorder = {9,3,15,20,7};
    vector<int> val;
    TreeNode* ret = s.ans1(preorder, inorder);
    s.myfrontTraverse(ret, val);
    s.show(val); val.clear();
    
}


int main(void){
    test1();

    return 0;
}